home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / solidbsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  15.5 KB  |  716 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. int leaffaces;                    // 4
  5. int nodefaces;                    // 4
  6. int splitnodes;                    // 4
  7.  
  8. int c_solid, c_empty, c_water;            // 12
  9.  
  10. bool usemidsplit;                // ?
  11.  
  12. //============================================================================
  13.  
  14. /*
  15.  * ==================
  16.  * FaceSide
  17.  * 
  18.  * For BSP hueristic
  19.  * ==================
  20.  */
  21. int FaceSide(register struct visfacet * in, register struct plane * split)
  22. {
  23.   int frontcount, backcount;
  24.   vec_t dot;
  25.   int i;
  26.   vec_t *p;
  27.  
  28.   frontcount = backcount = 0;
  29.  
  30. // axial planes are fast
  31.   if (split->type < 3)
  32.     for (i = 0, p = in->pts[0] + split->type; i < in->numpoints; i++, p += 3) {
  33.       if (*p > split->dist + ON_EPSILON) {
  34.     if (backcount)
  35.       return SIDE_ON;
  36.     frontcount = 1;
  37.       }
  38.       else if (*p < split->dist - ON_EPSILON) {
  39.     if (frontcount)
  40.       return SIDE_ON;
  41.     backcount = 1;
  42.       }
  43.     }
  44.   else
  45. // sloping planes take longer
  46.     for (i = 0, p = in->pts[0]; i < in->numpoints; i++, p += 3) {
  47.       dot = DotProduct(p, split->normal);
  48.       dot -= split->dist;
  49.       if (dot > ON_EPSILON) {
  50.     if (backcount)
  51.       return SIDE_ON;
  52.     frontcount = 1;
  53.       }
  54.       else if (dot < -ON_EPSILON) {
  55.     if (frontcount)
  56.       return SIDE_ON;
  57.     backcount = 1;
  58.       }
  59.     }
  60.  
  61.   if (!frontcount)
  62.     return SIDE_BACK;
  63.   if (!backcount)
  64.     return SIDE_FRONT;
  65.  
  66.   return SIDE_ON;
  67. }
  68.  
  69. /*
  70.  * ==================
  71.  * ChooseMidPlaneFromList
  72.  * 
  73.  * The clipping hull BSP doesn't worry about avoiding splits
  74.  * ==================
  75.  */
  76. struct surface *ChooseMidPlaneFromList(__memBase, register struct surface * surfaces, register vec3_t mins, register vec3_t maxs)
  77. {
  78.   int j, l;
  79.   struct surface *p, *bestsurface;
  80.   vec_t bestvalue, value, dist;
  81.   struct plane *plane;
  82.  
  83. //
  84.   // pick the plane that splits the least
  85.   //
  86.   bestvalue = 6 * 8192 * 8192;
  87.   bestsurface = NULL;
  88.  
  89.   for (p = surfaces; p; p = p->next) {
  90.     if (p->onnode)
  91.       continue;
  92.  
  93. #ifdef EXHAUSIVE_CHECK
  94.   if(p->planenum >= bspMem->numbrushplanes || p->planenum < 0)
  95.     Error("looking for nonexisting plane %d\n", p->planenum);
  96. #endif
  97.     plane = &bspMem->brushplanes[p->planenum];
  98.  
  99.     // check for axis aligned surfaces
  100.     l = plane->type;
  101.     if (l > PLANE_Z)
  102.       continue;
  103.  
  104.     //
  105.     // calculate the split metric along axis l, smaller values are better
  106.     //
  107.     value = 0;
  108.  
  109.     dist = plane->dist * plane->normal[l];
  110.     for (j = 0; j < 3; j++) {
  111.       if (j == l) {
  112.     value += (maxs[l] - dist) * (maxs[l] - dist);
  113.     value += (dist - mins[l]) * (dist - mins[l]);
  114.       }
  115.       else
  116.     value += 2 * (maxs[j] - mins[j]) * (maxs[j] - mins[j]);
  117.     }
  118.  
  119.     if (value > bestvalue)
  120.       continue;
  121.  
  122.     //
  123.     // currently the best!
  124.     //
  125.     bestvalue = value;
  126.     bestsurface = p;
  127.   }
  128.  
  129.   if (!bestsurface) {
  130.     for (p = surfaces; p; p = p->next)
  131.       if (!p->onnode)
  132.     return p;                                   // first valid surface
  133.  
  134.     Error("ChooseMidPlaneFromList: no valid planes");
  135.   }
  136.  
  137.   return bestsurface;
  138. }
  139.  
  140. /*
  141.  * ==================
  142.  * ChoosePlaneFromList
  143.  * 
  144.  * The real BSP hueristic
  145.  * ==================
  146.  */
  147. struct surface *ChoosePlaneFromList(__memBase, register struct surface * surfaces, register vec3_t mins, register vec3_t maxs, register bool usefloors)
  148. {
  149.   int j, k, l;
  150.   struct surface *p, *p2, *bestsurface;
  151.   vec_t bestvalue, bestdistribution, value, dist;
  152.   struct plane *plane;
  153.   struct visfacet *f;
  154.  
  155. //
  156.   // pick the plane that splits the least
  157.   //
  158.   bestvalue = 99999;
  159.   bestsurface = NULL;
  160.   bestdistribution = 9e30;
  161.  
  162.   for (p = surfaces; p; p = p->next) {
  163.     if (p->onnode)
  164.       continue;
  165.  
  166. #ifdef EXHAUSIVE_CHECK
  167.   if(p->planenum >= bspMem->numbrushplanes || p->planenum < 0)
  168.     Error("looking for nonexisting plane %d\n", p->planenum);
  169. #endif
  170.     plane = &bspMem->brushplanes[p->planenum];
  171.     k = 0;
  172.  
  173.     if (!usefloors && plane->normal[2] == 1)
  174.       continue;
  175.  
  176.     for (p2 = surfaces; p2; p2 = p2->next) {
  177.       if (p2 == p)
  178.     continue;
  179.       if (p2->onnode)
  180.     continue;
  181.  
  182.       for (f = p2->faces; f; f = f->next) {
  183.     if (FaceSide(f, plane) == SIDE_ON) {
  184.       k++;
  185.       if (k >= bestvalue)
  186.         break;
  187.     }
  188.  
  189.       }
  190.       if (k > bestvalue)
  191.     break;
  192.     }
  193.  
  194.     if (k > bestvalue)
  195.       continue;
  196.  
  197.     // if equal numbers, axial planes win, then decide on spatial subdivision
  198.  
  199.     if (k < bestvalue || (k == bestvalue && plane->type < PLANE_ANYX)) {
  200.       // check for axis aligned surfaces
  201.       l = plane->type;
  202.  
  203.       if (l <= PLANE_Z) {                               // axial aligned                                                
  204.     //
  205.     // calculate the split metric along axis l
  206.     //
  207.  
  208.     value = 0;
  209.  
  210.     for (j = 0; j < 3; j++) {
  211.       if (j == l) {
  212.         dist = plane->dist * plane->normal[l];
  213.         value += (maxs[l] - dist) * (maxs[l] - dist);
  214.         value += (dist - mins[l]) * (dist - mins[l]);
  215.       }
  216.       else
  217.         value += 2 * (maxs[j] - mins[j]) * (maxs[j] - mins[j]);
  218.     }
  219.  
  220.     if (value > bestdistribution && k == bestvalue)
  221.       continue;
  222.     bestdistribution = value;
  223.       }
  224.       //
  225.       // currently the best!
  226.       //
  227.       bestvalue = k;
  228.       bestsurface = p;
  229.     }
  230.  
  231.   }
  232.  
  233.   return bestsurface;
  234. }
  235.  
  236. /*
  237.  * ==================
  238.  * SelectPartition
  239.  * 
  240.  * Selects a surface from a linked list of surfaces to split the group on
  241.  * returns NULL if the surface list can not be divided any more (a leaf)
  242.  * ==================
  243.  */
  244. struct surface *SelectPartition(__memBase, register struct surface * surfaces)
  245. {
  246.   int i;
  247.   short int j;
  248.   vec3_t mins, maxs;
  249.   struct surface *p, *bestsurface;
  250.  
  251. //
  252.   // count onnode surfaces
  253.   //
  254.   i = 0;
  255.   bestsurface = NULL;
  256.   for (p = surfaces; p; p = p->next)
  257.     if (!p->onnode) {
  258.       i++;
  259.       bestsurface = p;
  260.     }
  261.  
  262.   if (i == 0)
  263.     return NULL;
  264.  
  265.   if (i == 1)
  266.     return bestsurface;                                   // this is a final split
  267.  
  268. //
  269.   // calculate a bounding box of the entire surfaceset
  270.   //
  271.   for (i = 0; i < 3; i++) {
  272.     mins[i] = 99999;
  273.     maxs[i] = -99999;
  274.   }
  275.  
  276.   for (p = surfaces; p; p = p->next)
  277.     for (j = 0; j < 3; j++) {
  278.       if (p->mins[j] < mins[j])
  279.     mins[j] = p->mins[j];
  280.       if (p->maxs[j] > maxs[j])
  281.     maxs[j] = p->maxs[j];
  282.     }
  283.  
  284.   if (usemidsplit)                                   // do fast way for clipping hull
  285.  
  286.     return ChooseMidPlaneFromList(bspMem, surfaces, mins, maxs);
  287.  
  288. // do slow way to save poly splits for drawing hull
  289. #if 0
  290.   bestsurface = ChoosePlaneFromList(surfaces, mins, maxs, FALSE);
  291.   if (bestsurface)
  292.     return bestsurface;
  293. #endif
  294.   return ChoosePlaneFromList(bspMem, surfaces, mins, maxs, TRUE);
  295. }
  296.  
  297. //============================================================================
  298.  
  299. /*
  300.  * =================
  301.  * CalcSurfaceInfo
  302.  * 
  303.  * Calculates the bounding box
  304.  * =================
  305.  */
  306. void CalcSurfaceInfo(register struct surface * surf)
  307. {
  308.   int i;
  309.   short int j;
  310.   struct visfacet *f;
  311.  
  312.   if (!surf->faces)
  313.     Error("CalcSurfaceInfo: surface without a face");
  314.  
  315. //
  316.   // calculate a bounding box
  317.   //
  318.   for (i = 0; i < 3; i++) {
  319.     surf->mins[i] = 99999;
  320.     surf->maxs[i] = -99999;
  321.   }
  322.  
  323.   for (f = surf->faces; f; f = f->next) {
  324.     if (f->contents[0] >= 0 || f->contents[1] >= 0)
  325.       Error("Bad contents");
  326.     for (i = 0; i < f->numpoints; i++)
  327.       for (j = 0; j < 3; j++) {
  328.     if (f->pts[i][j] < surf->mins[j])
  329.       surf->mins[j] = f->pts[i][j];
  330.     if (f->pts[i][j] > surf->maxs[j])
  331.       surf->maxs[j] = f->pts[i][j];
  332.       }
  333.   }
  334. }
  335.  
  336. /*
  337.  * ==================
  338.  * DividePlane
  339.  * ==================
  340.  */
  341. void DividePlane(__memBase, register struct surface * in, register struct plane * split, register struct surface ** front, register struct surface ** back)
  342. {
  343.   struct visfacet *facet, *next;
  344.   struct visfacet *frontlist, *backlist;
  345.   struct visfacet *frontfrag, *backfrag;
  346.   struct surface *news;
  347.   struct plane *inplane;
  348.  
  349. #ifdef EXHAUSIVE_CHECK
  350.   if(inplane->planenum >= bspMem->numbrushplanes || inplane->planenum < 0)
  351.     Error("looking for nonexisting plane %d\n", inplane->planenum);
  352. #endif
  353.   inplane = &bspMem->brushplanes[in->planenum];
  354.  
  355. // parallel case is easy
  356.   if (VectorCompare(inplane->normal, split->normal)) {
  357. // check for exactly on node
  358.     if (inplane->dist == split->dist) {                           // divide the facets to the front and back sides
  359.  
  360.       news = AllocSurface();
  361.       *news = *in;
  362.  
  363.       facet = in->faces;
  364.       in->faces = NULL;
  365.       news->faces = NULL;
  366.       in->onnode = news->onnode = TRUE;
  367.  
  368.       for (; facet; facet = next) {
  369.     next = facet->next;
  370.     if (facet->planeside == 1) {
  371.       facet->next = news->faces;
  372.       news->faces = facet;
  373.     }
  374.     else {
  375.       facet->next = in->faces;
  376.       in->faces = facet;
  377.     }
  378.       }
  379.  
  380.       if (in->faces)
  381.     *front = in;
  382.       else
  383.     *front = NULL;
  384.       if (news->faces)
  385.     *back = news;
  386.       else
  387.     *back = NULL;
  388.       return;
  389.     }
  390.  
  391.     if (inplane->dist > split->dist) {
  392.       *front = in;
  393.       *back = NULL;
  394.     }
  395.     else {
  396.       *front = NULL;
  397.       *back = in;
  398.     }
  399.     return;
  400.   }
  401.  
  402. // do a real split.  may still end up entirely on one side
  403.   // OPTIMIZE: use bounding box for fast test
  404.   frontlist = NULL;
  405.   backlist = NULL;
  406.  
  407.   for (facet = in->faces; facet; facet = next) {
  408.     next = facet->next;
  409.     SplitFace(facet, split, &frontfrag, &backfrag);
  410.     if (frontfrag) {
  411.       frontfrag->next = frontlist;
  412.       frontlist = frontfrag;
  413.     }
  414.     if (backfrag) {
  415.       backfrag->next = backlist;
  416.       backlist = backfrag;
  417.     }
  418.   }
  419.  
  420. // if nothing actually got split, just move the in plane
  421.  
  422.   if (frontlist == NULL) {
  423.     *front = NULL;
  424.     *back = in;
  425.     in->faces = backlist;
  426.     return;
  427.   }
  428.  
  429.   if (backlist == NULL) {
  430.     *front = in;
  431.     *back = NULL;
  432.     in->faces = frontlist;
  433.     return;
  434.   }
  435.  
  436. // stuff got split, so allocate one new plane and reuse in
  437.   news = AllocSurface();
  438.   *news = *in;
  439.   news->faces = backlist;
  440.   *back = news;
  441.  
  442.   in->faces = frontlist;
  443.   *front = in;
  444.  
  445. // recalc bboxes and flags
  446.   CalcSurfaceInfo(news);
  447.   CalcSurfaceInfo(in);
  448. }
  449.  
  450. /*
  451.  * ==================
  452.  * DivideNodeBounds
  453.  * ==================
  454.  */
  455. void DivideNodeBounds(register struct node * node, register struct plane * split)
  456. {
  457.   VectorCopy(node->mins, node->children[0]->mins);
  458.   VectorCopy(node->mins, node->children[1]->mins);
  459.   VectorCopy(node->maxs, node->children[0]->maxs);
  460.   VectorCopy(node->maxs, node->children[1]->maxs);
  461.  
  462. // OPTIMIZE: sloping cuts can give a better bbox than this...
  463.   if (split->type > 2)
  464.     return;
  465.  
  466.   node->children[0]->mins[split->type] =
  467.     node->children[1]->maxs[split->type] = split->dist;
  468. }
  469.  
  470. /*
  471.  * ==================
  472.  * LinkConvexFaces
  473.  * 
  474.  * Determines the contents of the leaf and creates the final list of
  475.  * original faces that have some fragment inside this leaf
  476.  * ==================
  477.  */
  478. void LinkConvexFaces(register struct surface * planelist, register struct node * leafnode)
  479. {
  480.   struct visfacet *f, *next;
  481.   struct surface *surf, *pnext;
  482.   int i, count;
  483.  
  484.   leafnode->faces = NULL;
  485.   leafnode->contents = 0;
  486.   leafnode->planenum = -1;
  487.  
  488.   count = 0;
  489.   for (surf = planelist; surf; surf = surf->next) {
  490.     for (f = surf->faces; f; f = f->next) {
  491.       count++;
  492.       if (!leafnode->contents)
  493.     leafnode->contents = f->contents[0];
  494.       else if (leafnode->contents != f->contents[0])
  495.     Error("Mixed face contents in leafnode");
  496.     }
  497.   }
  498.  
  499.   if (!leafnode->contents)
  500.     leafnode->contents = CONTENTS_SOLID;
  501.  
  502.   switch (leafnode->contents) {
  503.     case CONTENTS_EMPTY:
  504.       c_empty++;
  505.       break;
  506.     case CONTENTS_SOLID:
  507.       c_solid++;
  508.       break;
  509.     case CONTENTS_WATER:
  510.     case CONTENTS_SLIME:
  511.     case CONTENTS_LAVA:
  512.     case CONTENTS_SKY:
  513.       c_water++;
  514.       break;
  515.     default:
  516.       Error("LinkConvexFaces: bad contents number");
  517.   }
  518.  
  519. //
  520.   // write the list of faces, and free the originals
  521.   //
  522.   leaffaces += count;
  523.   if(!(leafnode->markfaces = (struct visfacet **)tmalloc(sizeof(struct visfacet *) * (count + 1))))
  524.     Error("LinkConvexFaces: failed to allocate markfaces\n");
  525.   i = 0;
  526.   for (surf = planelist; surf; surf = pnext) {
  527.     pnext = surf->next;
  528.     for (f = surf->faces; f; f = next) {
  529.       next = f->next;
  530.       leafnode->markfaces[i] = f->original;
  531.       i++;
  532.       FreeFace(f);
  533.     }
  534.     FreeSurface(surf);
  535.   }
  536.   leafnode->markfaces[i] = NULL;                           // sentinal
  537.  
  538. }
  539.  
  540. /*
  541.  * ==================
  542.  * LinkNodeFaces
  543.  * 
  544.  * Returns a duplicated list of all faces on surface
  545.  * ==================
  546.  */
  547. struct visfacet *LinkNodeFaces(__memBase, register struct surface * surface)
  548. {
  549.   struct visfacet *f, *new, **prevptr;
  550.   struct visfacet *list;
  551.  
  552.   list = NULL;
  553.  
  554. // subdivide
  555.   prevptr = &surface->faces;
  556.   while (1) {
  557.     f = *prevptr;
  558.     if (!f)
  559.       break;
  560.     SubdivideFace(bspMem, f, prevptr);
  561.     f = *prevptr;
  562.     prevptr = &f->next;
  563.   }
  564.  
  565. // copy
  566.   for (f = surface->faces; f; f = f->next) {
  567.     nodefaces++;
  568.     new = AllocFace(f->numpoints);
  569.     CopyFace(new, f);
  570.     f->original = new;
  571.     new->next = list;
  572.     list = new;
  573.   }
  574.  
  575.   return list;
  576. }
  577.  
  578. /*
  579.  * ==================
  580.  * PartitionSurfaces
  581.  * ==================
  582.  */
  583. void PartitionSurfaces(__memBase, register struct surface * surfaces, register struct node * node)
  584. {
  585.   struct surface *split, *p, *next;
  586.   struct surface *frontlist, *backlist;
  587.   struct surface *frontfrag, *backfrag;
  588.   struct plane *splitplane;
  589.  
  590.   split = SelectPartition(bspMem, surfaces);
  591.   if (!split) {                                       // this is a leaf node
  592.  
  593.     node->planenum = PLANENUM_LEAF;
  594.     LinkConvexFaces(surfaces, node);
  595.     return;
  596.   }
  597.  
  598.   splitnodes++;
  599.   node->faces = LinkNodeFaces(bspMem, split);
  600.   node->children[0] = AllocNode();
  601.   node->children[1] = AllocNode();
  602.   node->planenum = split->planenum;
  603.  
  604. #ifdef EXHAUSIVE_CHECK
  605.   if(split->planenum >= bspMem->numbrushplanes || split->planenum < 0)
  606.     Error("looking for nonexisting plane %d\n", split->planenum);
  607. #endif
  608.   splitplane = &bspMem->brushplanes[split->planenum];
  609.  
  610.   DivideNodeBounds(node, splitplane);
  611.  
  612. //
  613.   // multiple surfaces, so split all the polysurfaces into front and back lists
  614.   //
  615.   frontlist = NULL;
  616.   backlist = NULL;
  617.  
  618.   for (p = surfaces; p; p = next) {
  619.     next = p->next;
  620.     DividePlane(bspMem, p, splitplane, &frontfrag, &backfrag);
  621.     if (frontfrag && backfrag) {
  622.       // the plane was split, which may expose oportunities to merge
  623.       // adjacent faces into a single face
  624.       //                      MergePlaneFaces (frontfrag);
  625.       //                      MergePlaneFaces (backfrag);
  626.     }
  627.  
  628.     if (frontfrag) {
  629.       if (!frontfrag->faces)
  630.     Error("surface with no faces");
  631.       frontfrag->next = frontlist;
  632.       frontlist = frontfrag;
  633.     }
  634.     if (backfrag) {
  635.       if (!backfrag->faces)
  636.     Error("surface with no faces");
  637.       backfrag->next = backlist;
  638.       backlist = backfrag;
  639.     }
  640.   }
  641.  
  642.   PartitionSurfaces(bspMem, frontlist, node->children[0]);
  643.   PartitionSurfaces(bspMem, backlist, node->children[1]);
  644. }
  645.  
  646. /*
  647.  * ==================
  648.  * DrawSurface
  649.  * ==================
  650.  */
  651. void DrawSurface(register struct surface * surf)
  652. {
  653.   struct visfacet *f;
  654.  
  655.   for (f = surf->faces; f; f = f->next)
  656.     Draw_DrawFace(f);
  657. }
  658.  
  659. /*
  660.  * ==================
  661.  * DrawSurfaceList
  662.  * ==================
  663.  */
  664. void DrawSurfaceList(register struct surface * surf)
  665. {
  666.   Draw_ClearWindow();
  667.   while (surf) {
  668.     DrawSurface(surf);
  669.     surf = surf->next;
  670.   }
  671. }
  672.  
  673. /*
  674.  * ==================
  675.  * SolidBSP
  676.  * ==================
  677.  */
  678. struct node *SolidBSP(__memBase, struct surface * surfhead, bool midsplit)
  679. {
  680.   short int i;
  681.   struct node *headnode;
  682.  
  683.   mprintf("----- SolidBSP ----------\n");
  684.  
  685.   headnode = AllocNode();
  686.   usemidsplit = midsplit;
  687.  
  688. //
  689.   // calculate a bounding box for the entire model
  690.   //
  691.   for (i = 0; i < 3; i++) {
  692.     headnode->mins[i] = brushset->mins[i] - SIDESPACE;
  693.     headnode->maxs[i] = brushset->maxs[i] + SIDESPACE;
  694.   }
  695.  
  696. //
  697.   // recursively partition everything
  698.   //
  699.   Draw_ClearWindow();
  700.   splitnodes = 0;
  701.   leaffaces = 0;
  702.   nodefaces = 0;
  703.   c_solid = c_empty = c_water = 0;
  704.  
  705.   PartitionSurfaces(bspMem, surfhead, headnode);
  706.  
  707.   mprintf("%5i split nodes\n", splitnodes);
  708.   mprintf("%5i solid leafs\n", c_solid);
  709.   mprintf("%5i empty leafs\n", c_empty);
  710.   mprintf("%5i water leafs\n", c_water);
  711.   mprintf("%5i leaffaces\n", leaffaces);
  712.   mprintf("%5i nodefaces\n", nodefaces);
  713.  
  714.   return headnode;
  715. }
  716.